/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import com.leetCode.structure.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/14
 */
public class _15_104_MaximumDepthOfBinaryTree {

    // !_!
    public static int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth2(root.left), maxDepth2(root.right));
    }

    public static int maxDepth1(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node;
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return level;
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        List<Integer> levels = new ArrayList<>();
        dfs(root, 0, levels);
        int max = Integer.MIN_VALUE, value;
        for (int i = 0; i < levels.size(); i++) {
            value = levels.get(i);
            if (value > max) max = value;
        }
        return max;
    }

    private static void dfs(TreeNode node, int level, List<Integer> levels) {
        if (node == null) {
            levels.add(level);
            return;
        }
        dfs(node.left, level + 1, levels);
        dfs(node.right, level + 1, levels);
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(9);
        TreeNode t3 = new TreeNode(20);
        t1.left = t2;
        t1.right = t3;
        TreeNode t4 = new TreeNode(15);
        TreeNode t5 = new TreeNode(7);
        t3.left = t4;
        t3.right = t5;
//        System.out.println(maxDepth1(t1));
        System.out.println(maxDepth2(t1));
    }
}
